In a typical computing environment, one or more software applications may run concurrently with each application likely having numerous tasks requiring access to the CPU for the processing of these tasks. Further, each concurrent application may each have any number of concurrent threads competing for CPU access. For example, in an object-oriented application running inside a Java Virtual Machine (“VM”), a task may include a call to a method, the creation of an object instance, or a mathematical calculation. Each of these tasks would require access to the CPU for processing, as would tasks from the other applications in the environment.
In order for a CPU to handle the volume of tasks vying for processing time, a scheduler is often used. Most operating systems (“OS”) include one or more internal task schedulers to manage and prioritize the tasks needing resources from the CPU. The primary function of such a scheduler is to intercept CPU requests from the various applications for their desired tasks and prioritize which tasks will run in what order.
FIG. 1 is a block diagram illustrating a typical task scheduler included in an OS. In the computing environment 100, task scheduler 101 is responsible for receiving requests from applications running on the OS for tasks A-E for access to CPU 155. Tasks A-E may be requested by one application running in the computer environment 100 or may be requested by several applications. The scheduler 101 may simultaneously receive CPU requests to perform tasks A 110, B 120, C 130, D 140 and E 150. Scheduler 101 may use one or more algorithms to determine the priority in which the tasks will be performed. Once a priority is determined, the tasks are moved into a queue 175 to await their turn for access to the CPU 155. In this example, task D 142 is placed into the queue 175 first, followed by task E 152, task B 122, task A 112 and task C 132. Once placed in the queue 175, task D 142 will have access to CPU 155 first. Once task D 142 begins processing by CPU 155, the task leaves the queue 175, resulting in task E 152 becoming first in line. In the meantime, it is likely that additional tasks (not shown) have requested access to the CPU 155. The scheduler 101 will continue executing the one or more algorithms to determine the priority of each task requesting access to the CPU 155.
Much of the difficulty of efficiently scheduling tasks is maintaining adequate distribution of CPU time amongst the applications needing CPU services. In other words, if there are five applications running at once, the scheduler should maintain fairness by scheduling tasks from all five applications such that no one application is given too much or too little CPU time. The notion of fairness may be defined in the context of a specified deployment of one or more applications.
In some computer environments, a scheduler may maintain fairness by time-slicing or otherwise parsing the requesting tasks to ensure that each task is performed equally. For example, in a router environment, the scheduler may read the first 100 bytes of a first incoming packet and send it to the CPU for processing. The scheduler may then read the first 100 bytes of a second incoming packet and send that packet to the CPU. In this manner, the scheduler may continue to cycle through the incoming packets, 100 bytes at a time to process the packets. Thus, each packet receives equal processing time with no single packet delaying the processing of the other packets. Similarly, in a multithreaded processing environment, the scheduler may time-slice each task to run on each thread for 200 milliseconds. Thus, the scheduler maintains fairness in the amount of processing time each task receives by providing the same amount of processing time on each thread.
However, in some computing environments, the tasks requesting processing time on the CPU cannot be time-sliced. These tasks, once started, must continue until finished. Using the example of FIG. 1, task D 142 must be completed before task E 152 can begin. Thus, in a single-processor system in this environment, only a single task can run at one time. Multi-processor, multi-core and multi-threading environments allow for multiple tasks to run concurrently. However each processor core is still limited to running a single task at a time. Thus, if a certain task requires a significant amount of time to process, the processor would be unable to process other important tasks until the current task is completed. This may delay applications accessing the processors, freezing the applications until the tasks of other applications are processed.
While some computing environments may accept the freezing of the application, other environments may require a low-latency execution of the requested tasks. One example of such an environment is a Massive Multi-player Online Role Playing Game (“MMORPG”) environment. Because the enjoyment of the online game may relate to how smoothly the game is presented to the online game player, it may be necessary to provide a low-latency configuration such that the online game does not freeze during gameplay.
One approach for ensuring scheduling fairness in a computing environment where tasks cannot be time-sliced is to provide the scheduler with the time required to process the task when the task is requested. For example, a task may be called by an application to be processed on the CPU that requires 3 milliseconds of time. The scheduler may intercept the request and schedule 3 milliseconds of time on the CPU. In this manner, the scheduler may prioritize the tasks to efficiently complete each task without reserving the CPU for too long a time. However, this approach requires the application to provide the processing time for each task when the task is requested, resulting in longer processing time for the application and more complex application design.